#include "heap.h"
#include <iterator>
#include <ostream>


heap::heap(const std::vector<int>& nums){
    nums_ = nums;
    const int n = nums_.size();
    for(int idx = n/2-1; idx >= 0; --idx)
        siftdown(idx);
}
int heap::top(){
    return nums_[0];
}
void heap::pop(){
    nums_[0] = nums_.back();
    nums_.pop_back();
    siftdown(0);
}
bool heap::empty(){
    return nums_.empty();
}
int heap::size(){
    return nums_.size();
}
void heap::insert(int num){
    nums_.push_back(num);
    int idx = nums_.size()-1;
    siftup(idx);
}

/**
 * @brief 上浮操作
 * @param idx: 待上浮的元素序号
 * @note 如果父节点比当前节点大，则交换，确保父节点的元素小于子节点
 */
void heap::siftup(int idx){
    const int n = nums_.size();
    while(idx >= 0){
        int parent = (idx-1)/2;
        if(nums_[parent] > nums_[idx]){
            std::swap(nums_[parent],nums_[idx]);
            idx = parent;
        }else{
            break;
        }
    }
}
/**
 * @brief 下沉函数
 * @param idx: 待下沉的元素序号
 * @note 如果子节点比当前节点小，则交换，确保父节点的元素小于子节点
 */
void heap::siftdown(int idx){
    const int n = nums_.size();
    while(idx < n){ // 从idx节点开始遍历，一直到叶子节点
        int child = 2 * idx + 1;
        if(child >= n){
            break;
        }
        if(child + 1 < n && nums_[child+1] < nums_[child]){
            ++child;
        }
        if(nums_[child] < nums_[idx]){
            std::swap(nums_[child],nums_[idx]);
            idx = child;
        }else{
            break;
        }
    }
}

std::ostream& operator<<(std::ostream& os, const heap& h){
    std::copy(h.nums_.begin(),h.nums_.end(), std::ostream_iterator<int>(os,","));
    return os;
}